/*
 * @lc app=leetcode.cn id=42 lang=cpp
 *
 * [42] 接雨水
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

// @lc code=start
class Solution {
public:
    int trap(vector<int>& height) {
        int length = height.size();     // 保存天数
        int result = 0;
        int tmpHeight = 0;
        vector<int> leftMax(length, 0);
        vector<int> rightMax(length, 0);

        // 正序遍历，记录从左侧开始的最大高度
        tmpHeight = 0;
        for (int i = 0; i < length; i++) {
            tmpHeight = max(tmpHeight, height[i]);
            leftMax[i] = tmpHeight;
        }

        // 逆序遍历，记录从右侧开始的最大高度
        tmpHeight = 0;
        for (int i = length - 1; i >= 0; i--) {
            tmpHeight = max(tmpHeight, height[i]);
            rightMax[i] = tmpHeight;
        }

        for (int i = 0; i < length; i++) {
            result += max(min(leftMax[i], rightMax[i]) - height[i], 0);
        }

        return result;
    }
};
// @lc code=end

